\chapter{Algoritma Transform and Conquer}


\ifthenelse{\boolean{adaTIU}}{
	\begin{footnotesize}
	  \begin{description}
	    \item[Tujuan Pembelajaran]:
	    \begin{itemize}
				\item Memberikan penjelasan mengenai teknik Transform and Conquer dan masalah yang dapat diselesaikan dengan teknik tersebut
				\item Memberikan penjelasan mengenai berbagai teknik komputasi pada matriks
				\item Memberikan penjelasan mengenai heap dan berbagai algoritma yang berhubungan dengan heap
			\end{itemize}
			\item[Setelah menyelesaikan modul ini mahasiswa diharapkan dapat]:
			\begin{itemize}
				\item Melakukan teknik pencarian persamaan simultan dengan Eliminasi Gauss
				\item Melakukan teknik operasi matriks dengan komposisi LU
				\item Melakukan pencarian inversi dan determinan matriks
				\item Menjelaskan pengertian heap
				\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas penyusunan heap
				\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas pengurutan heap
				\item Menggunakan sifat heap untuk ADT priority queue
			\end{itemize}
			\item[Kata kunci]:
			Eliminasi Gauss, determinan, heap, inversi, komposisi LU, matriks, teknik transform and conquer, pengurutan heap, priority queue
		\end{description}
	\end{footnotesize}
}


\section{Pendahuluan}

Tidak setiap masalah komputasi selalu cocok untuk diselesaikan dengan menggunakan teknik-teknik pemecahan masalah yang sudah kita bahas sebelumnya. Kadang kala kita perlu mengubah representasi masalah yang diberikan ke dalam bentuk lain agar pemecahan masalahnya dapat dilakukan dengan lebih mudah. Dengan mengubah representasi masalah ke dalam bentuk lain, berarti kita melakukan sebuah proses transformasi. Kelompok masalah komputasi yang diselesaikan dengan cara seperti ini tergolong ke dalam masalah-masalah \index{transform and conquer@\emph{Transform and Conquer}} \emph{Transform and Conquer}.

\begin{figure}
  \begin{center}
    \includegraphics{transform-and-conquer-method}
  \end{center}
  \label{fig:transform-and-conquer-method}
  \caption{Metodologi pemecahan masalah secara transform and conquer.}
\end{figure}

Secara ilustratif, teknik pemecahan \emph{transform and conquer} terlihat dalam Gambar~\ref{fig:transform-and-conquer-method}. Algoritma dengan teknik transform and conquer akan menyelesaikan suatu permasalahan secara tidak langsung, yaitu pertama mengubah permasalahan semula menjadi permasalahan dalam bentuk lain yang lebih sederhana, dan kemudian menyelesaikan msalah yang lebih sederhana tersebut.

Eliminasi Gauss merupakan salah satu masalah yang dapat diselesaikan dengan menggunakan teknik transform and conquer ini. Pada eliminasi Gauss, sistem persamaan yang ditulis dalam bentuk matriks asal, diubah bentuk menjadi matriks segitiga, yang penyelesaiannya dapat dengan mudah dicari. Selain eliminasi Gauss tersebut, teknik operasi matriks dengan dekomposisi LU, pencarian inversi dan determinan matriks juga merupakan contoh dari penyelesaian masalah yang menggunakan teknik transform and conquer. Di samping masalah-masalah tersebut, dalam bab ini dibahas juga teknik pengurutan dengan menggunakan \emph{heap} dan penggunaan \emph{priority queue}.


\section{Pemecahan sistem persamaan linear dengan Eliminasi Gauss}

Di SMU, anda pernah mempelajari bagaimana menyelesaikan sebuah persoalan seperti berikut:
\[
  \begin{array}{cccc}
    2x & + y & = & 1 \\
    4x & - y & = & 5 \\
  \end{array}
\]
Dalam persoalan semacam ini anda diminta untuk mencari nilai-nilai variabel $x$ dan $y$ yang memenuhi kedua persamaan tersebut. Masalah ini disebut sebagai \index{sistem persamaan linier@{Sistem Persamaan Linier}} Sistem Persamaan Linier, karena memuat lebih dari satu persamaan di dalam satu kesatuan sistem. Persamaan-persamaan yang ada di dalam sistem ini adalah persamaan linier, karena variabel-variabel yang terlibat di dalam sistem adalah variabel linier \footnote{Berbeda dengan persamaan kuadrat misalnya, yang memiliki bentuk umum $ax^2 + bx +c = 0$ di mana salah satu suku di dalam persamaan tersebut tidak linier ($x^2$).}. Dalam contoh ini, kita memiliki sebuah sistem persamaan linier yang terdiri atas dua persamaan dengan dua variabel.

Salah satu cara yang dapat digunakan untuk menyelesaikan persoalan di atas adalah dengan menggunakan teknik \index{substitusi} substitusi. Sistem persamaan di atas terdiri atas dua persamaan:
\begin{equation} \label{eq:spl-1-a}
  2x + y = 1
\end{equation}
\begin{equation} \label{eq:spl-2-a}
  4x - y = 5
\end{equation}
Persamaan \ref{eq:spl-1-a} dapat dinyatakan sebagai
\begin{equation} \label{eq:spl-1-b}
  y = 1 - 2x
\end{equation}
yang dapat kita substitusikan ke dalam persamaan~\ref{eq:spl-2-a}, sehingga persamaan~\ref{eq:spl-2-a} dapat dinyatakan sebagai
\[
  4x - ( 1 - 2x ) = 5
\]

Dengan cara mensubstitusi variabel $y$ seperti ini, kita bisa mendapatkan nilai variabel $x = 1$ yang kemudian kita substitusikan balik ke dalam persamaan~\ref{eq:spl-1-b} untuk mendapatkan
\[
  y = 1 - 2 \cdot 1 = -1
\]

Secara umum sebuah sistem persamaan linier tidak hanya terdiri atas dua persamaan dengan dua variabel, tapi dapat terdiri atas $n$ persamaan dengan $n$ variabel. 
\begin{equation} \label{eq:spl-generic}
	\begin{array}{ccccccccc}
		a_{11}x_1 & + & a_{12}x_2 & + & \ldots & + & a_{1n}x_n & = & b_1 \\
		a_{21}x_1 & + & a_{22}x_2 & + & \ldots & + & a_{2n}x_n & = & b_2 \\
		\vdots &      &           &   & \ddots &   &           &   & \vdots \\
		a_{n1}x_1 & + & a_{n2}x_2 & + & \ldots & + & a_{nn}x_n & = & b_n \\
	\end{array}
\end{equation}
Jika jumlah persamaan dan jumlah variabel semakin banyak, maka kita dapat menggunakan teknik substitusi untuk mencari nilai-nilai dari setiap variabel dalam sistem persamaan tersebut. Namun tentu saja cara seperti ini memakan waktu yang lama karena kita perlu melakukan substitusi balik berulang-ulang~\footnote{Lihat Latihan~\ref{ex:substitusi-spl}.}. Karenanya kita memerlukan sebuah cara lain yang lebih efisien.

Sistem persamaan linier seperti~\ref{eq:spl-generic} dapat dinyatakan sebagai sebuah perklian antara matrix $A$ dengan matriks kolom $x$ yang menghasilkan matriks kolom $b$. Di mana
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaauaabeqabiaaaeaacaWGbbGaeyypa0daba
% WaaeWaaeaafaqabeabeaaaaaqaaiaadggadaWgaaWcbaGaaGymaiaa
% igdaaeqaaaGcbaGaamyyamaaBaaaleaacaaIXaGaaGOmaaqabaaake
% aacqWIMaYsaeaacaWGHbWaaSbaaSqaaiaaigdacaWGUbaabeaaaOqa
% aiaadggadaWgaaWcbaGaaGOmaiaaigdaaeqaaaGcbaGaamyyamaaBa
% aaleaacaaIYaGaaGOmaaqabaaakeaaaeaacaWGHbWaaSbaaSqaaiaa
% ikdacaWGUbaabeaaaOqaaiabl6UinbqaaaqaaiablgVipbqaaiabl6
% UinbqaaiaadggadaWgaaWcbaGaamOBaiaaigdaaeqaaaGcbaGaamyy
% amaaBaaaleaacaWGUbGaaGOmaaqabaaakeaacqWIMaYsaeaacaWGHb
% WaaSbaaSqaaiaad6gacaWGUbaabeaaaaaakiaawIcacaGLPaaaaaaa
% aa!55B1!
\[
\begin{array}{*{20}c}
   {A = } & {\left( {\begin{array}{*{20}c}
   {a_{11} } & {a_{12} } &  \ldots  & {a_{1n} }  \\
   {a_{21} } & {a_{22} } & {} & {a_{2n} }  \\
    \vdots  & {} &  \ddots  &  \vdots   \\
   {a_{n1} } & {a_{n2} } &  \ldots  & {a_{nn} }  \\
\end{array}} \right)}  \\
\end{array}
\]

% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaauaabeqabiaaaeaacaWG4bGaeyypa0daba
% WaaeWaaeaafaqabeabbaaaaeaacaWG4bWaaSbaaSqaaiaaigdaaeqa
% aaGcbaGaamiEamaaBaaaleaacaaIYaaabeaaaOqaaiabl6Uinbqaai
% aadIhadaWgaaWcbaGaamOBaaqabaaaaaGccaGLOaGaayzkaaaaaaaa
% !3D3F!
\[
\begin{array}{*{20}c}
   {x = } & {\left( {\begin{array}{*{20}c}
   {x_1 }  \\
   {x_2 }  \\
    \vdots   \\
   {x_n }  \\
\end{array}} \right)}  \\
\end{array}
\]
dan
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaauaabeqabiaaaeaacaWGIbGaeyypa0daba
% WaaeWaaeaafaqabeabbaaaaeaacaWGIbWaaSbaaSqaaiaaigdaaeqa
% aaGcbaGaamOyamaaBaaaleaacaaIYaaabeaaaOqaaiabl6Uinbqaai
% aadkgadaWgaaWcbaGaamOBaaqabaaaaaGccaGLOaGaayzkaaaaaaaa
% !3CE7!
\[
\begin{array}{*{20}c}
   {b = } & {\left( {\begin{array}{*{20}c}
   {b_1 }  \\
   {b_2 }  \\
    \vdots   \\
   {b_n }  \\
\end{array}} \right)}  \\
\end{array}
\]
Sehingga persamaan~\ref{eq:spl-generic} dapat dinyatakan sebagai
\begin{equation} \label{eq:spl-matrix-multiplication}
  Ax = b
\end{equation}

Perhatikan bahwa sampai di sini kita telah melakukan sebuah transformasi dari sebuah sistem persamaan linier menjadi sebuah sistem perkalian matriks.

Untuk memberi gambaran nyata bagaimana metode \emph{transform and conquer} bekerja, kita dapat mencari solusi sistem persamaan linier
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaauaabeqadCaaaaqaaiaaikdacaWG4bWaaS
% baaSqaaiaaigdaaeqaaaGcbaGaeyOeI0cabaGaamiEamaaBaaaleaa
% caaIYaaabeaaaOqaaiabgUcaRaqaaiaadIhadaWgaaWcbaGaaG4maa
% qabaaakeaacqGH9aqpaeaacaaIXaaabaGaaGinaiaadIhadaWgaaWc
% baGaaGymaaqabaaakeaacqGHRaWkaeaacaWG4bWaaSbaaSqaaiaaik
% daaeqaaaGcbaGaeyOeI0cabaGaamiEamaaBaaaleaacaaIZaaabeaa
% aOqaaiabg2da9aqaaiaaiwdaaeaacaWG4bWaaSbaaSqaaiaaigdaae
% qaaaGcbaGaey4kaScabaGaamiEamaaBaaaleaacaaIYaaabeaaaOqa
% aiabgUcaRaqaaiaadIhadaWgaaWcbaGaaG4maaqabaaakeaacqGH9a
% qpaeaacaaIWaaaaaaa!4F54!
\begin{equation} \label{eq:sample-spl}
\begin{array}{*{20}c}
   {2x_1 } &  -  & {x_2 } &  +  & {x_3 } &  =  & 1  \\
   {4x_1 } &  +  & {x_2 } &  -  & {x_3 } &  =  & 5  \\
   {x_1 } &  +  & {x_2 } &  +  & {x_3 } &  =  & 0  \\
\end{array}
\end{equation}
dengan teknik transform and conquer ini. Sistem persamaan~\ref{eq:sample-spl} kita transformasikan menjadi sebuah sistem perkalian matriks
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaamaabmaabaqbaeqabmWaaaqaaiaaikdaae
% aacqGHsislcaaIXaaabaGaaGymaaqaaiaaisdaaeaacaaIXaaabaGa
% eyOeI0IaaGymaaqaaiaaigdaaeaacaaIXaaabaGaaGymaaaaaiaawI
% cacaGLPaaadaqadaqaauaabeqadeaaaeaacaWG4bWaaSbaaSqaaiaa
% igdaaeqaaaGcbaGaamiEamaaBaaaleaacaaIYaaabeaaaOqaaiaadI
% hadaWgaaWcbaGaaG4maaqabaaaaaGccaGLOaGaayzkaaGaeyypa0Za
% aeWaaeaafaqabeWabaaabaGaaGymaaqaaiaaiwdaaeaacaaIWaaaaa
% GaayjkaiaawMcaaaaa!47EC!
\[
\left( {\begin{array}{*{20}c}
   2 & { - 1} & 1  \\
   4 & 1 & { - 1}  \\
   1 & 1 & 1  \\
\end{array}} \right)\left( {\begin{array}{*{20}c}
   {x_1 }  \\
   {x_2 }  \\
   {x_3 }  \\
\end{array}} \right) = \left( {\begin{array}{*{20}c}
   1  \\
   5  \\
   0  \\
\end{array}} \right)
\]

Untuk mencari solusi dari sistem perkalian matriks ini, kita menggunakan teknik \index{eliminasi gauss@eliminasi Gauss} eliminasi Gauss. Langkah pertama yang perlu kita lakukan adalah membuat sebuah matriks yang diperluas, atau \index{augmented matrix@\emph{augmented matrix}} \emph{augmented matrix}. \emph{Augmented matrix} tidak lain adalah matriks yang didapatkan dengan menggandengkan antara matriks $A$ dengan matriks $b$
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaamaabmaabaqbaeqabmabaaaabaGaaGOmaa
% qaaiabgkHiTiaaigdaaeaacaaIXaaabaGaaGymaaqaaiaaisdaaeaa
% caaIXaaabaGaeyOeI0IaaGymaaqaaiaaiwdaaeaacaaIXaaabaGaaG
% ymaaqaaiaaigdaaeaacaaIWaaaaaGaayjkaiaawMcaaaaa!3DED!
\[
\left( {\begin{array}{*{20}c}
   2 & { - 1} & 1 & 1  \\
   4 & 1 & { - 1} & 5  \\
   1 & 1 & 1 & 0  \\
\end{array}} \right)
\]
Eliminasi Gauss melakukan serangkaian operasi yang dikenal sebagai operasi elementer terhadap \emph{augmented matrix} ini untuk mengubah matriks tersebut menjadi berbentuk matriks segitiga atas \index{upper triangular matrix@\emph{upper triangular matrix}} \index{matrix@\emph{matrix}!upper triangular@\emph{upper triangular}} (\emph{upper triangular matrix}).


Berbagai cara dapat dilakukan untuk menyelesaikan sistem persamaan tersebut, dimana Eliminasi Gauss merupakan cara yang dapat dikategorikan cukup mudah untuk dilakukan. Dengan cara eliminasi Gauss, sistem persamaan linear tersebut akan diubah menjadi bentuk persamaan A'x = b', sebagai berikut:
\[
\begin{array}{ccccccccc}
	a'_{11}x_1 & + & a'_{12}x_2 & + & \ldots & + & a'_{1n}x_n & = & b'_1 \\
	           &   & a'_{22}x_2 & + & \ldots & + & a'_{2n}x_n & = & b'_2 \\
	           &   &            &   & \ddots &   &            &   & \vdots \\
	           &   &            &   &        &   & a'_{nn}x_n & = & b'_n \\
\end{array}
\]
Dengan demikian maka terlihat bahwa xn dapat dengan mudah untuk dicari dengan membagi b'n dengan a'nn, selanjutnya xn-1 dicari dari baris sebelumnya dengan hasil yang telah didapat. Demikian seterusnya hingga x2 dan x1 dapat diketahui.

Karena dalam melakukan eliminasi tersebut matriks kolom b, selalu diperlakukan sama dengan komponen matriks lainnya, maka dalam implementasi program matriks b, selalu akan disatukan sebagai bagian dari matriks A, sehingga jumlah kolom matriks A menjadi n+1.


\section{Operasi matriks dengan komposisi LU}

Bila proses eliminasi Gauss yang dilakukan diperhatikan lebih lanjut, terlihat bahwa perubahan matriks A menjadi matriks segitiga A' disebabkan karena operasi pengurangan elemen ai, j dengan dengan ai, j-k yang dikalikan konstanta pi, j tertentu. Bila komponen pi, j  tersebut disusun sebagai matriks dengan komponen diagonal adalah 1, maka matriks segitiga yang terjadi disebut sebagai matriks segitiga bawah (lower-triangle) dari matriks A semula, yang biasa disimbolkan sebagai matriks L . Selanjutnya bila matriks L dikalikan Matriks A', maka akan didapat matriks A semula, sehingga matriks segitiga A' juga dikenal sebagai matriks segitiga atas (upper-triangle) dari A dan lazim disimbolkan sebagai matriks U. Berdasarkan hal tersebut maka matriks A juga dapat dianggap sebagai perkalian antara matriks L dengan U, yang secara simbolis ditulis A = LU.

Berdasarkan sifat tersebut, sistem persamaan linear Ax = b, dapat ditulis sebagai LUx = b. Bila saja Ux dihitung terlebih dahulu sebagai y, maka persamaan semula tersebut dapat ditulis sebagai Ly = b. Dalam pemrograman persamaan, karena matriks L mempunyai komponen diagonal 1, maka matriks y dengan mudah dapat dicari dari persamaan Ly = b. Selanjutnya karena Ux = y dimana y telah diketahui dan U merupakan matriks segitiga, maka dengan cara yang serupa x dapat diketahui.


\section{Pencarian matriks invers}

Berdasarkan definisi inverse dari matriks bujur sangkar A adalah matriks A-1 yang berdimensi sama, sedemikian rupa sehingga perkalian AA-1 = I, dimana I adalah matriks identitas dengan dimensi yang sama, yaitu matriks yang semua elemennya 0, selain elemen diagonalnya yang bernilai 1.

Dari sifat inverse tersebut, sesungguhnya mencari A-1, tidak lain adalah mencari matriks X, dimana setiap Xj yang merupakan elemen kolom X, mempunyai sifat AXj = Ij, dimana Ij adalah matriks kolom ke j dari matriks identitas I. Dengan mengetahui sifat tersebut, maka pencarian matriks inverse tidak lain adalah mencari sejumlah solusi dari sistem persamaan linear, dimana eliminasi Gauss, atau kombinasinya dengan matriks dengan komposisi LU, dapat dipergunakan untuk hal tersebut.


\section{Pencarian Determinan}

Hal lain yang merupakan kekhususan adri suatu matriks bujur sangkar adalah nilai determinan dari matriks tersebut. Secara definisi dterminan dari matriks A, dapat didefinisikan dengan pengertian rekursif:
\[
\mathrm{det}(A) = \Sigma s_j a_{1j} \mathrm{det}(A_j) \mathrm{untuk} j = 1 \mathrm{s.d.} n
\]
dengan
\[
\begin{array}{cl}
	s_j	&	+1 \mathrm{untuk} j \mathrm{gasal dan} -1 \mathrm{untuk} j \mathrm{genap} \\
	A_j	&	\mathrm{matriks (n-1) x (n-1), yang didapat dengan menghilangkan baris ke-1 dan kolom ke j}
\end{array}
\]
Dari formula tersebut terlihat bahwa pencarian determinan suatu matriks A adalah suatu proses yang rumit. Namun bila matriks tersebut terlebih dahulu diubah menjadi matriks segitiga atas U dengan eliminasi Gauss, maka determinan matriks A tidak lain adalah perkalian elemen diagonal dari matriks segitiga atas U yang didapat


\section{Heap}

\index{heap@\emph{heap}} Heap merupakan \index{binary tree@\emph{binary tree}} \emph{binary tree} yang bersifat khusus, baik struktur maupun isi datanya. Sebuah \emph{heap} memiliki struktur yang disebut \index{complete binary tree@\emph{complete binary tree}} \index{binary tree@\emph{binary tree}!complete@\emph{complete}} \emph{complete binary tree}, di mana semua \emph{node} dimasukkan ke dalam setiap level dari \emph{tree} secara berurut dari kiri ke kanan. Selain itu suatu \emph{heap} juga harus memenuhi sifat yang disebut sebagai \index{heap property@\emph{heap property}} \emph{heap property}, ditunjukkan secara matematis pada Persamaan~\ref{eq:heap-property}. Sifat ini menyatakan \emph{key} dari \emph{parent} selalu lebih besar dari atau sama dengan \emph{key} dari anak-anaknya. \emph{Heap} yang mempunyai sifat berkebalikan dengan sifat ini, yaitu \emph{key} dari \emph{parent} selalu lebih kecil dari atau sama dengan \emph{key} dari anak-anaknya lazim disebut sebagai \index{min-heap@\emph{min-heap}} \emph{min-heap}.
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaaiaabIeacaqGLbGaaeyyaiaabchacaGGBb
% GaaeiuaiaabggacaqGYbGaaeyzaiaab6gacaqG0bGaaiikaiaadMga
% caGGPaGaaiyxaiabgsMiJkaabIeacaqGLbGaaeyyaiaabchacaGGBb
% GaamyAaiaac2faaaa!469E!
\begin{equation} \label{eq:heap-property}
{\rm Heap}[{\rm Parent}(i)] \le {\rm Heap}[i]
\end{equation}

Karena sifat struktur heap yang demikian, maka heap dapat direpresentasikan dengan struktur data yang sederhana, yaitu array dengan anggota sebanyak jumlah node pada heap terebut. Representasi heap dengan array ini dimungkinkan karena index array dapat dipergunakan untuk menyatakan nomor node dan isi dari array menyatakan key dari node tersebut. Selain itu agar informasi mengenai jumlah anggota yang ada pada heap dapat  diketahui, maka pada heap diperlukan elemen tambahan yang bertipe integer untuk menyatakan jumlah elemen elemen dari heap (length) yang ada.

Dengan representasi array yang dimulai dengan index 0, maka akan terdapat hubungan indeks dari \emph{node parent} dengan \emph{node} anak kiri dan \emph{node} anak kanannya sebagai hubungan berikut:
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaaiaabcfacaqGHbGaaeOCaiaabwgacaqGUb
% GaaeiDaiaacIcacaWGPbGaaiykaiabg2da9maagmaabaWaaSaaaeaa
% caWGPbGaeyOeI0IaaGymaaqaaiaaikdaaaaacaGLWJVaay5+4daaaa!42E7!
\begin{equation} \label{eq:parent-heap}
{\rm Parent}(i) = \left\lfloor {\frac{{i - 1}}{2}} \right\rfloor 
\end{equation}
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaaiaabUeacaqGPbGaaeOCaiaabMgacaGGOa
% GaamyAaiaacMcacqGH9aqpcaaIYaGaey41aqRaamyAaiabgUcaRiaa
% igdaaaa!3DEA!
\begin{equation} \label{eq:left-child-heap}
{\rm Kiri}(i) = 2 \times i + 1
\end{equation}
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaaiaabUeacaqGHbGaaeOBaiaabggacaqGUb
% GaaiikaiaadMgacaGGPaGaeyypa0JaaGOmaiabgEna0kaacIcacaWG
% PbGaey4kaSIaaGymaiaacMcaaaa!4020!
\begin{equation} \label{eq:right-child-heap}
{\rm Kanan}(i) = 2 \times (i + 1)
\end{equation}

\subsection{Membangun heap}

Seperti telah dijelaskan sebelumnya struktur data suatu heap tidak lain adalah suatu array. Oleh karena itu membangun heap tidak lain adalah menempatkan isi dari array tersebut sehingga memenuhi sifat heap tersebut. Apabila heap tersebut ingin dibangun mulai dari awal, yaitu dengan memasukkan anggota ke-1, 2 \(\ldots\) sampai dengan anggota terakhir, maka proses tersebut dapat dilakukan dengan menyisipkan setiap anggota baru pada posisi yang benar, yang tidak menyebabkan hilangnya sifat heap. Algoritma yang dapat menambah anggota heap ini dapat dilihat pada Algoritme~\ref{alg:tambah-heap}.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE TambahAnggotaHeap (H, k)
	\STATE baris 01	heapSize[H] = heapSize[H]+ 1
	\STATE baris 02	i = heapSize[H]
	\STATE baris 03	Lakukan selama (i>1 dan H[Parent(i)]< k)
	\STATE baris 04		H[i] = H[Parent(i)]
	\STATE baris 05		i = Parent(i)
	\STATE baris 06	H[i] = k
\end{algorithmic}
\caption{Algoritma Penambahan anggota heap.} \label{alg:tambah-heap}
\end{algorithm}

Cara lain untuk membangun heap, adalah dengan mengubah array yang sudah ada, agar bersifat heap. Hal terakhir ini dapat dilakukan dengan cara memeriksa setiap anggota apakah sudah memenuhi sifat heap (key dari parent selalu lebih besar dari atau sama dengan key dari anak-anaknya), apabila belum maka lakukan perbaikan posisi. Algoritma untuk mengatur sifat heap dari node ke - i diperlihatkan pada Algoritme~\ref{alg:atur-heap}.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE JadikanHeap (H, i)
	\STATE baris 01	ki = Kiri(i)
	\STATE baris 02	ka = Kanan(i)
	\STATE baris 03	Jika ki<= heapSize[H] dan H[ki]> H[i]
	\STATE baris 04		bsr = ki
	\STATE baris 05	Jika tidak 
	\STATE baris 06		bsr = ka
	\STATE baris 07	Jika ka<= heapSize[H] dan H[ka]> H[bsr]
	\STATE baris 08		bsr = ka
	\STATE baris 09	Jika bsr <> H[bsr]
	\STATE baris 10		Tukar (H[i], H[bsr])
	\STATE baris 11		JadikanHeap (H, bsr)
\end{algorithmic}
\caption{Algoritma Pengaturan sifat heap.} \label{alg:atur-heap}
\end{algorithm}

Dengan demikian maka untuk pembentukan heap dari suatu array dapat dilakukan dengan algoritma seperti pada Algoritme~\ref{alg:bentuk-heap}.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE BentukHeap (H)
	\STATE baris 01	heapSize[H] = length[H]
	\STATE baris 02	Lakukan mulai floor (length[H]/2) turun s.d 1
	\STATE baris 03		JadikanHeap (H, i)
\end{algorithmic}
\caption{Algoritma Pembentukan Heap.} \label{alg:bentuk-heap}
\end{algorithm}

\subsection{Pengurutan heap}

Heap Sort atau pengurutan heap merupakan teknik pengurutan yang memanfaatkan sifat heap. Sekumpulan data dalam array yang semula belum terurut akan diubah (transform) menjadi heap. Selanjutnya karena anggota heap terbesar akan selalu merupakan root dari heap, maka satu persatu root tersebut diambil untuk disusun menjadi data terurut, dan kemudian dilakukan pengaturan kembali heap, dengan jumlah anggota yang satu lebih sedikit dari semula. Bila hal tersebut terus menerus dilakukan maka pada saat habis anggota heap, maka akan terdapat data yang telah terurut.

Berdasarkan hal tersebut, maka dapat ditulis algoritma pengurutan heap seperti pada Algoritme~\ref{alg:heap-sort}.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE PengurutanHeap (H)
	\STATE baris 01	BentukHeap (H)
	\STATE baris 02	lh = length[H]
	\STATE baris 03	Lakukan mulai dari i = lh turun s.d 2
	\STATE baris 04		Tukar (H[1], H[i])
	\STATE baris 05		heapSize[H] = heapSize[H] - 1
	\STATE baris 06		JadikanHeap (H, 1)
\end{algorithmic}
\caption{Algoritma Pengurutan Heap.} \label{alg:heap-sort}
\end{algorithm}


\section{Priority Queue}

Sifat dari heap dapat dipergunakan untuk merepresentasikan suatu tipe data abstrak yang disebut priority queue. Priority queue merupakan suatu antrian, dimana pelayanan yang diberikan tergantung dari prioritas dari setiap anggotanya. Anggota yang mempunyai prioritas yang lebih tinggi akan didahulukan dalam pelayanannya.

Operasi-operasi yang diperlukan pada tipe data abstrak ini adalah tambah anggota (seperti enqueue pada queue), dan ambil terbesar (seperti dequeue pada queue). Algoritma penambahan anggota dapat dilihat pada gambar 07-01, sedangkan algoritma ambil terbesar dapat dilihat pada Algoritme~\ref{alg:ambil-terbesar}.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE AmbilTerbesar (H)
	\STATE baris 01	Jika heapSize[H] < 1 return ("underflow")
	\STATE baris 02	besar = H[1]
	\STATE baris 03	H[1] = H[heapSize[H]]
	\STATE baris 04	heapSize[H] = heapSize[H] -1
	\STATE baris 05	JadikanHeap (H, 1)
	\STATE baris 06	return besar
\end{algorithmic}
\caption{Algoritma Pengambilan anggota terbesar.} \label{alg:ambil-terbesar}
\end{algorithm}


\section{Soal-soal latihan dan bahan diskusi}

\renewcounter{chapter}
\begin{ExerciseList}%[counter={latihan}]
  \Exercise \label{ex:substitusi-spl} Carilah nilai-nilai ketiga variabel $x$, $y$, dan $z$ dalam sistem persamaan linier berikut ini. Substitusikan variabel $z$ dari persamaan~\ref{eq:ex:substitusi-spl-1} untuk mendapatkan sebuah sistem persamaan linier baru yang terdiri atas dua persamaan dan dua variabel $x$ dan $y$. Kemudian lakukanlah substitusi untuk variabel $y$ hingga anda mendapatkan nilai setiap variabel.
  \begin{equation} \label{eq:ex:substitusi-spl-1}
    x + y + z = 2
  \end{equation}
  \begin{equation}
    2x + y + z = 3
  \end{equation}
  \begin{equation}
    x - y + z = 8
  \end{equation}
  
  \Exercise Selesaikan sistem persamaan dalam Latihan~\ref{ex:substitusi-spl} dengan menggunakan metode eliminasi Gauss.
  
  \Exercise Carilah invers matriks $A$ dari sistem persamaan linier
	\[
	\begin{array}{ccccccc}
	  x_1 & + & x_2 & + & x_3 & = & 2 \\
		2 x_1 & + & x_2 & + & x_3 &	= & 3 \\
		x_1 & - & x_2 & + & 3 x_3	& = & 8 \\
	\end{array}
	\]
	
	\Exercise Buatlah sebuah program untuk mencari solusi persamaan linier pada Soal~\ref{ex:substitusi-spl} dengan menggunakan teknik eliminasi Gauss.
	
	\Exercise Selesaikan persoalan nomor~\ref{ex:substitusi-spl} dengan menggunakan teknik dekomposisi LU, baik secara manual maupun dengan program.
	
	\Exercise Pergunakan metode eliminasi Gauss untuk mengetahui apakah sebuah matriks bersifat singular atau tidak.
	
	\Exercise Selesaikan sistem persamaan linier berikut dengan cara Cramer:
	\[
	\begin{array}{ccccccc}
		2 x_1 & - & x_2 & + & x_3	& = & 1 \\
		4 x_1 & + & x_2 & - & x_3	& = & 3 \\
		x_1 & - & x_2 & + & x_3	& = & 0 \\
	\end{array}
	\]
	
	\Exercise Buat program untuk mencari solusi persamaan linear pada no 5 dengan cara Cramer.
	
	\Exercise Buatlah heap dengan anggota 1,8,6,5,3,7 dan 4 dengan cara:
	\begin{enumerate}
		\item memasukkan keseluruhan data tersebut kedalam array, untuk kemudian dijadikan heap.
		\item memasukkan satu persatu anggota tersebut pada heap (mulai dari kheap kosong).
	\end{enumerate}
	
	\Exercise Tuliskan sebuah fungsi dalam bahasa pemrograman Java atau C++ untuk memeriksa apakah suatu array merupakan heap atau bukan.
	
	\Exercise Lakukan pengurutan heap dari huruf-huruf berikut: S, O, R, T, I, N dan G.
\end{ExerciseList}
